package problems.practice;

/**
 * 5. 最长回文子串
 * @author habitplus
 * @since 2022/8/9 14:09
 */
public class T5 {

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;

        char[] chs = s.toCharArray();
        int n = chs.length;
        // dp[i][j] = true 表示 s[i...j] 为回文串
        boolean[][] dp = new boolean[n][n];

        // 记录最大长度，和起始位置
        int maxLen = 0, start = 0;

        for (int i = 0; i < n; ++i) dp[i][i] = true;

        // 先枚举字符串的长度
        for (int k = 2; k <= n; ++k) {
            // 枚举左边界
            for (int i = 0; i < n; ++i) {
                // 右边界
                int j = i + k - 1;
                if (j >= n) break;


                // 如果chs[i] != chs[j]，则 chs[i...j] 必不可能是回文串
                if (chs[i] != chs[j]) dp[i][j] = false;
                // 只有3个字符，且首尾两个字符还相等
                else if (j - i < 3) dp[i][j] = true;
                // 取决于里面一层，即 chs[i+1...j-1] 是否为回文串
                else dp[i][j] = dp[i + 1][j - 1];


                // 只要 dp[i][j] == true 成立，就表示子串 s[i..L] 是回文，此时可能需要更新最大长度和起始位置
                if (dp[i][j] && maxLen < j - i + 1) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }

        return s.substring(start, start + maxLen);
    }
}
